% Version control information:
%\svnid{$Id: ramificacion_poda.tex 5 2009-03-29 23:59:23Z asalber $
%
\subsection{Ramificación y poda}
%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Técnica de ramificación y poda}
La técnica de \textbf{ramificación y poda} es básicamente una mejora de la técnica de vuelta atrás que consiste en un recorrido dinámico más eficiente del espacio de búsqueda.

\medskip
La principal diferencia es que, mientras que la técnica de vuelta atrás realiza un recorrido ciego del espacio de búsqueda, la técnica de ramificación y poda realiza un recorrido informado.

\medskip
En un recorrido ciego, bien sea en profundidad o en anchura, se conoce perfectamente el siguiente nodo a visitar (siguiente hijo o hermano del nodo actual), es decir, el orden del recorrido está establecido a priori, mientras que en un recorrido informado, se busca el siguiente nodo más prometedor en base a la información de que se disponga.

\medskip
Se aplica fundamentalmente a problemas de optimización con restricciones, donde el espacio de búsqueda es un árbol.
\end{frame} 


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Nodos prometedores}
Diremos que un nodo del espacio de búsqueda es \textbf{prometedor}, si la información que tenemos de ese nodo en el recorrido indica que expandiéndolo se puede conseguir una solución mejor que la mejor solución obtenida hasta el momento.

\medskip
Esta información puede provenir de la evaluación del camino ya recorrido hasta el nodo, o bien  de la evaluación de los caminos quedan por recorrer desde el nodo a posibles soluciones.

\medskip
Para guiar la búsqueda es fundamental disponer de una función que, no sólo diga si un nodo es o no prometedor, sino que además estime lo prometedor que es. Esta función se conoce como \textbf{función de prioridad}.
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Tipos de nodos en el espacio de búsqueda}
El espacio de búsqueda se representa mediante un árbol en el que hay tres clases de nodos:
\begin{itemize}
\item \textbf{Nodo vivo}: Es un nodo hasta el cual la solución en curso es factible, prometedora, y del que no se han generado aún todos sus hijos (no se ha completado la solución).\\
Indican caminos abiertos de búsqueda.
\item \textbf{Nodo muerto}: Es un nodo del que no van a generarse más hijos porque, o bien ya se han generado todos sus hijos, o bien no es factible, o bien no es prometedor. \\
Indican caminos cerrados de búsqueda. 
\item \textbf{Nodo en expansión}: Es aquel del que se están generando sus hijos en un determinado instante.
\end{itemize}
En un determinado instante de la búsqueda puede haber muchos nodos vivos y muertos pero sólo uno en expansión.
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Funcionamiento de la técnica de vuelta atrás}
En la técnica de vuelta atrás, cada vez que se generaba un hijo del nodo en expansión, este pasaba inmediatamente a ser el nodo en expansión. En consecuencia, los únicos nodos vivos son los que están en el camino de la raíz al nodo en expansión.

\medskip
Por el contrario, en la técnica de ramificación y poda se generan todos los hijos del nodo en expansión antes de que cualquier otro nodo vivo pase a ser el nuevo nodo en expansión. Esto supone que puede haber nodos vivos en distintos caminos y tendremos que guardar la lista de nodos vivos en alguna estructura de datos (suelen ser \emph{pilas o colas con prioridad}).
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Estrategias de búsqueda}
Existen diferentes estrategias para elegir el siguiente nodo en expansión de la lista de nodos vivos:
\begin{itemize}
\item \textbf{Más antiguo}: Se elige como nodo en expansión el más antiguo de la lista. En este caso la lista se implementa como una cola.	Produce un recorrido en anchura.\\
\item  \textbf{Menos antiguo}: Se elige como nodo en expansión el menos antiguo de la lista. En este caso la lista se implementa como una pila. Produce un recorrido en profundidad.
\item \textbf{Más prometedor}: Se elige como nodo de expansión el nodo más prometedor de la lista. La lista se implementa como una cola con prioridades, donde la prioridad de un nodo es lo prometedor que es. Produce un recorrido informado y \alert{\emph{¡es el que suele utilizar la técnica de ramificación y poda!}}
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Algoritmo genérico de ramificación y poda}
El siguiente algoritmo calcula la solución óptima de un problema de optimización mediante la técnica de ramificación y poda:
\begin{lstlisting}
funcion ramificacion_y_poda(T sol[n], conjunto<T> D)
  inicializar(C); insertar(C, <sol, 0, prioridad(sol,0)>)
  mientras no_vacia(C) hacer
    <sol, k> = primero(C)
    para_todo x en D hacer
      sol[k] = x
      si completable(sol,k) & coste(sol,k) < mcoste entonces
        si solucion(sol) entonces
          mejor_solucion = sol; mcoste = coste(sol,k)
        si_no insertar(C, <sol, k+1, prioridad(sol,k+1)>)
      fin_si
    fin_para_todo
  fin_mientras
  devolver (mejor_solucion, mcoste)
fin_funcion
\end{lstlisting}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Algoritmo genérico de ramificación y poda}
En el algoritmo anterior se tiene que:
\begin{itemize}
\item \texttt{C} es una cola con prioridades, es decir, sus elementos están ordenados de acuerdo a sus prioridades.
\item \texttt{prioridad(sol,k)} es una función que devuelve la prioridad de un nodo vivo, que será lo prometedor que es. Esta función sirve para dirigir la búsqueda y llegar pronto a la solución óptima.
\item \texttt{completable(sol,k)} es una función que comprueba si la solución parcial correspondiente al nodo en expansión es satisface las restricciones del problema. Cuando no se cumplen se realiza una \emph{poda por no factibilidad} y el nodo en expansión deja de expandirse y pasa a ser un nodo muerto.
\item \texttt{coste(sol,k)} es una función que nos da una cota del coste de todas las soluciones que podrían generarse a partir de la solución parcial correspondiente al nodo en expansión. Cuando \texttt{coste(sol,k)$\leq$ mcoste} no tiene sentido seguir expandiendo el nodo y se realizar una \emph{poda basada en la mejor solución}.\\ 
Habitualmente la función de prioridad también suele ser la función de coste.
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Coste temporal de ramificación y poda}
El coste temporal de un algoritmo que utilice la técnica de ramificación y poda, depende fundamentalmente de:
\begin{itemize}
\item El número de nodos del espacio de búsqueda que se visitan $v(n)$. Que depende a su vez de lo buenas que sean las funciones completable y coste para hacer podas, y lo buena que sea la función prioridad para dirigir la búsqueda.
\item El coste de las funciones prioridad, completable y coste en cada nodo $p(n)$.
\item El coste del mantenimiento de la cola con prioridad.
\end{itemize}
En total suele ser $O(p(n)v(n))$.
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema de la mochila entera}
\framesubtitle{Ejemplo de ramificación y poda}
Recordemos el espacio de búsqueda asociado a este problema. 

\medskip
Si tenemos $n$ objetos y representamos el contenido de la mochila con un
vector \texttt{sol[$n$]=\{$x_1,\ldots,x_n$\}} donde
\[
x_i = 
\begin{cases}
0 & \mbox{si el objeto $i$ no está en la mochila}\\
1 & \mbox{si el objeto $i$ si está en la mochila}
\end{cases}
\]
entonces el espacio de búsqueda asociado es
\begin{center}
\psset{treesep=0.2cm,levelsep=0.5cm,nodesep=1pt}
\newcommand{\dotedge}{\ncline[linestyle=dotted]}
\pstree[thislevelsep=0]{\Tn}{
\pstree{\Tp}{ 
	\pstree{\TR{0}}{
       \pstree{\TR{0}}{\psset{linestyle=dotted}
       			\pstree{\TR{}}{\psset{linestyle=solid}\TR{0}\TR{1}} 
       }
       \tspace{0.5cm}
       \pstree{\TR{1}}{\psset{linestyle=dotted}
       			\pstree{\TR{}}{\psset{linestyle=solid}\TR{0}\TR{1}} 
       }
    }
    \tspace{2cm}
    \pstree{\TR{1}}{
       \pstree{\TR{0}}{\psset{linestyle=dotted}
       			\pstree{\TR{}}{\psset{linestyle=solid}\TR{0}\TR{1}} 
       }
       \tspace{0.5cm}
       \pstree{\TR{1}}{\psset{linestyle=dotted}
       			\pstree{\TR{}}{\psset{linestyle=solid}\TR{0}\TR{1}} 
       }
    }
    
}
\tspace{0.5cm}
\pstree[linestyle=none]{\TR{}}{
	\pstree{\TR{Objeto 1}}{
		\pstree{\TR{Objeto 2}}{
			\pstree{\TR{$\vdots$}}{\TR{Objeto $n$}}
		}
	}
}
}
\end{center}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{El problema de la mochila entera}
\framesubtitle{Estructura de un nodo}
Cada nodo del espacio de búsqueda debe contener la información necesaria para generar sus hijos o para decidir si es solución o no puede serlo.

\medskip
Utilizaremos la siguiente estructura de datos en C++:
\begin{lstlisting}
class nodo{
private:
  int numel;  // Numero total de objetos
  int *sol;  // Vector solucion
  int actual;  // Objeto hasta el que se han tomado decisiones
  float pes;  // Peso restante de la mochila
  float val;  // Valor de la mochila
  float prio;  // Prioridad del nodo
}
\end{lstlisting}

Los valores de \texttt{pes} y \texttt{val} podrían calcularse sin necesidad de almacenarlos pero es más eficiente pasarlos a los hijos. Esto se conoce como \textbf{marcaje}.
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{El problema de la mochila entera}
\framesubtitle{Función de coste y prioridad}
La siguiente función en C++ se utiliza como función de coste para la poda y también como función de prioridad para dirigir la búsqueda:
\begin{lstlisting}
float cotavalor(nodo *x){
nodo *sig;
  int i = x->etapa();
  if (i >= x->numobjetos() || x->peso() == 0)
    return x->valor();
  else if (weight[i] > x->peso())
    return x->valor() + x->peso() / weight[i] * value[i];
  else {
    sig = new nodo(*x);
    sig->suma_valor(valor[i]);
    sig->resta_peso(peso[i]);
    sig->sig_etapa();
    return cotavalor(sig);
  }
}
\end{lstlisting}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{El problema de la mochila entera}
\framesubtitle{Algoritmo con ramificación y poda}
La siguiente función en C++ resuelve el problema de la mochila entera con la técnica de ramificación y poda:
\begin{lstlisting}
nodo* rellenar(int n, float pesomax){
  priority_queue<nodo*, vector<nodo*>, mayor_pri> c;
  nodo raiz(n, pesomax);
  nodo *hijo, *nodoexp, *solucion;
  c.push(&raiz); solucion = &raiz;
  while (!c.empty()){
    nodoexp = c.top();
    c.pop();
    if (nodoexp->prioridad() >= solucion->valor())
      for (int j=1; j>=0; j--){
        hijo = new nodo(*nodoexp);
        hijo->fija_objeto(j);
        hijo->suma_valor(j*valor[hijo->etapa()]);
        hijo->resta_peso(j*peso[hijo->etapa()]);  
        hijo->sig_etapa();
\end{lstlisting}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{El problema de la mochila entera}
\framesubtitle{Algoritmo con ramificación y poda}
La siguiente función en C++ resuelve el problema de la mochila entera con la técnica de ramificación y poda:
\begin{lstlisting}
        hijo->fija_prio(cotaval(hijo));
        if (hijo->peso() >= 0 &&
            solucion->valor() < hijo->prioridad())
          if (hijo->solucion()) solucion = hijo;
          else c.push(hijo);
      }
    delete nodoexp;
  } 
  return solucion;
}
\end{lstlisting}
Siendo \texttt{c} una cola con prioridad implementada en la librería de plantillas estándar de C++, con el orden
\begin{lstlisting}
bool mayor_pri::operator()(nodo *a,nodo *b){
  return (a->prioridad() < b->prioridad());
}
\end{lstlisting}
Y siendo \texttt{valor[]} el vector de valores de los objetos) y \texttt{peso[]} el de los pesos.
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema de la mochila entera}
\framesubtitle{Ejemplo con la técnica de ramificación y poda}
Si hay 5 objetos de valores \texttt{valor[]=\{30,40,60,10,20\}} y pesos
\texttt{peso[]=\{6,10,20,5,15\}}, y una mochila de capacidad 30, entonces la
función realiza el siguiente recorrido del espacio de búsqueda:  
\begin{center}
\psset{treesep=0.15cm,levelsep=0.9cm,nodesep=1pt}
\pstree[thislevelsep=0]{\Tn}{
\pstree{\Tp}{ 
	\pstree{\TR{1}\tlput{\footnotesize$c=112$}}{
       \pstree{\TR{1}\tlput{\footnotesize$c=112$}}{
       		\pstree[linestyle=dashed,linecolor=red]{\TR{1}\tlput{\footnotesize$c=118$}}{
				\pstree{\TR{1}}{\TR{1}\TR{0}}
				\pstree{\TR{0}}{\TR{1}\TR{0}}
			}
			\pstree[linestyle=dashed,linecolor=orange]{\TR{0}\trput{\footnotesize$c=92$}}{
				\pstree{\TR{1}}{\TR{1}\TR{0}}
				\pstree{\TR{0}}{\TR{1}\TR{0}}
			} 
       }
       \pstree[linestyle=dashed,linecolor=orange]{\TR{0}\trput{\footnotesize$c=98$}}{ \pstree{\TR{1}}{
				\pstree{\TR{1}}{\TR{1}\TR{0}}			
				\pstree{\TR{0}}{\TR{1}\TR{0}} 
			} 
			\pstree{\TR{0}}{
				\pstree{\TR{1}}{\TR{1}\TR{0}}
				\pstree{\TR{0}}{\TR{1}\TR{0}}
			} 
       }
    }
    \pstree{\TR{0}\trput{\footnotesize$c=100$}}{
       \pstree{\TR{1}\tlput{\footnotesize$c=100$}}{
       		\pstree{\TR{1}\tlput{\footnotesize$c=100$}}{
				\pstree[linestyle=dashed,linecolor=red]{\TR{1}\tlput{\footnotesize$103$}}{\TR{1}\TR{0}}
				\pstree{\TR{0}\trput{\footnotesize$100$}}{
					\TR{1}
					\pstree[levelsep=0.5cm,linecolor=green,arrows=->]{\TR{0}}{\TR{\textcolor{green}{100}}}
				}
			}
			\pstree[linestyle=dashed,linecolor=orange]{\TR{0}\trput{\footnotesize$c=70$}}{
				\pstree{\TR{1}}{\TR{1}\TR{0}}
				\pstree{\TR{0}}{\TR{1}\TR{0}}
			} 
       }
       \pstree[linestyle=dashed,linecolor=orange]{\TR{0}\trput{\footnotesize$c=76.67$}}{
       		\pstree{\TR{1}}{
				\pstree{\TR{1}}{\TR{1}\TR{0}}
				\pstree{\TR{0}}{\TR{1}\TR{0}}
			}
			\pstree{\TR{0}}{
				\pstree{\TR{1}}{\TR{1}\TR{0}}
				\pstree{\TR{0}}{\TR{1}\TR{0}}
			} 
       }
    }
} 
\tspace{0.1cm}
\pstree[linestyle=none]{\TR{}}{ \footnotesize
	\pstree{\TR{\parbox{1.5cm}{Objeto 1\\ p=6,v=30}}}{
		\pstree{\TR{\parbox{1.5cm}{Objeto 2\\ p=10,v=40}}}{
			\pstree{\TR{\parbox{1.5cm}{Objeto 3\\ p=20,v=60}}}{
				\pstree{\TR{\parbox{1.5cm}{Objeto 4\\ p=5,v=10}}}{
					\pstree[levelsep=0.5cm]{\TR{\parbox{1.5cm}{Objeto 5\\ p=15,v=20}}}{
						\TR{maxval}
					} 
				}
			}
		}
	}
}
}
\end{center}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema del viajante}
Recordemos que se trata de buscar el camino más corto para visitar $n$ ciudades y volver a la ciudad de partida sin pasar dos veces por la misma ciudad.

\medskip
Ya vimos una solución con programación dinámica, pero requería un coste en memoria excesivo.
\[
\psmatrix[colsep=1.5cm,rowsep=1cm,nodesep=3pt]
& \textcolor{red}{3}\raisebox{-0.2cm}{\includegraphics[scale=0.5]{img/ciudad1}}  \\
\textcolor{red}{2}\raisebox{-0.2cm}{\includegraphics[scale=0.5]{img/ciudad1}} & & \raisebox{-0.2cm}{\includegraphics[scale=0.5]{img/ciudad1}}\textcolor{red}{0}\\
& \textcolor{red}{1}\raisebox{-0.2cm}{\includegraphics[scale=0.5]{img/ciudad1}}
\ncline{->}{2,1}{2,3}^{\qquad 2}
\ncline{->}{1,2}{2,1}<{4}
\ncline{->}{1,2}{2,3}>{2}
\ncline{->}{1,2}{3,2}<{\raisebox{1cm}{5}}
\ncline{->}{2,3}{3,2}>{3}
\ncline{->}{3,2}{2,1}<{4}
\ncarc[arcangle=30]{->}{2,1}{1,2}<{6}
\ncarc[arcangle=-30]{->}{2,3}{1,2}>{3}
\ncarc[arcangle=-30]{->}{2,1}{3,2}<{6}
\ncarc[arcangle=-30]{->}{3,2}{2,3}>{5}
\endpsmatrix
\qquad
\raisebox{1cm}{\includegraphics[scale=0.5]{img/viajante}}
\]
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema del viajante}
\framesubtitle{Modelización mediante grafos}
Como ya vimos, representamos cada ciudad mediante un nodo de un grafo y cada camino como
una arista dirigida, tendremos un grafo dirigido $G=(V,A)$ donde:
\begin{itemize}
  \item $V={1,…,n}$ es el conjunto de vértices (ciudades).
  \item $A$ es el conjunto de aristas $(i,j)$ con $i,j \in V$ (caminos).
  \item $D(i,j)$ es la longitud de $(i,j)$ si $(i,j)\in A$, o $\infty$ si
  $(i,j)\not\in A$.
\end{itemize}
\[
\scalebox{0.7}{
\psmatrix[colsep=1.5cm,rowsep=1cm,nodesep=3pt]
& \textcolor{red}{3}\raisebox{-0.2cm}{\includegraphics[scale=0.5]{img/ciudad1}}  \\
\textcolor{red}{2}\raisebox{-0.2cm}{\includegraphics[scale=0.5]{img/ciudad1}} & & \raisebox{-0.2cm}{\includegraphics[scale=0.5]{img/ciudad1}}\textcolor{red}{0}\\
& \textcolor{red}{1}\raisebox{-0.2cm}{\includegraphics[scale=0.5]{img/ciudad1}}
\ncline{->}{2,1}{2,3}^{\qquad 2}
\ncline{->}{1,2}{2,1}<{4}
\ncline{->}{1,2}{2,3}>{2}
\ncline{->}{1,2}{3,2}<{\raisebox{1cm}{5}}
\ncline{->}{2,3}{3,2}>{3}
\ncline{->}{3,2}{2,1}<{4}
\ncarc[arcangle=30]{->}{2,1}{1,2}<{6}
\ncarc[arcangle=-30]{->}{2,3}{1,2}>{3}
\ncarc[arcangle=-30]{->}{2,1}{3,2}<{6}
\ncarc[arcangle=-30]{->}{3,2}{2,3}>{5}
\endpsmatrix
}
\quad
\begin{array}[b]{|c|c|c|c|c|}
\hline
\mbox{De}\backslash\mbox{A} & 0 & 1 & 2 & 3 \\
\hline 
0 & \infty & 3 & \infty & 3 \\
\hline 
1 & 5 & \infty & 4 & \infty \\
\hline 
2 & 2 & 6 & \infty & 6 \\
\hline 
3 & 2 & 5 & 4 & \infty\\
\hline
\end{array}
\]
Representaremos la solución con un vector \texttt{sol[n]} que almacenará en la
posición $i$, la ciudad a visitar en $i$-ésimo lugar. 
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema del viajante}
\framesubtitle{Espacio de búsqueda}
El conjunto de posibles soluciones serán todas las  permutaciones de las $n-1$
ciudades que hay que visitar, es decir $(n-1)!$. Si por ejemplo, tenemos 4
ciudades, el árbol del espacio de búsqueda tendrá 3!= 6 ramas, que serán
\begin{center}
\newcommand{\Tlabel}[1]{\tlput{\footnotesize #1}}
\pstree[thislinestyle=none,thislevelsep=0]{}{
\pstree[nodesep=2pt,levelsep=1cm,arrows=->,treenodesize=0.5cm]{\TR{0}}{ 
	\pstree{\TR{1}}{ 
    	\pstree{\TR{1}}{ 
    		\pstree{\TR{2}}{ 
    			\TR{0} 
    		}
    	} 
    	\pstree{\TR{2}}{ 
    		\pstree{\TR{1}}{
       			\TR{0}
       		}
       	}
	}
	\pstree{\TR{2}}{ 
    	\pstree{\TR{1}}{ 
    		\pstree{\TR{2}}{ 
    			\TR{0} 
    		}
    	} 
    	\pstree{\TR{2}}{ 
    		\pstree{\TR{1}}{
       			\TR{0}
       		}
       	}
	}	
    \pstree{\TR{3}}{ 
    	\pstree{\TR{1}}{ 
    		\pstree{\TR{2}}{ 
    			\TR{0} 
    		}
    	} 
    	\pstree{\TR{2}}{ 
    		\pstree{\TR{1}}{
       			\TR{0}
       		}
       	}
	}
}
\pstree[linestyle=none,nodesep=2pt,levelsep=1cm]{\TR{Origen}}{
	\pstree{\TR{1ª visita}}{
		\pstree{\TR{2ª visita}}{
			\pstree{\TR{3ª visita}}{
			 	\TR{Destino}
			 }
		}
	}
}
}
\end{center}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema del viajante}
\framesubtitle{Determinación de la función de prioridad}
Para que la poda basada en la mejor solución sea efectiva, conviene utilizar un
buena función que acote inferiormente el coste del camino mínimo para una
solución en curso. 

\medskip
Una cota muy sencilla podría ser la suma de los caminos
ya elegidos. Parece lógico también utilizar esta cota como prioridad, ya que,
en principio, los caminos más cortos recorridos hasta el momento, parecen los
más prometedores y deben intentarse en primer lugar. 
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{El problema de la mochila entera}
\framesubtitle{Estructura de un nodo}
Para representar los nodos del espacio de búsqueda utilizaremos la siguiente
clase en C++:
\begin{lstlisting}
class nodo{
  int numel;  // Numero de ciudades
  int *camino;  // Ciudades visitadas hasta el momento
  int actual;  // Etapa actual del viaje
  float dist;  // Distancia recorrida hasta el momento
public:
  nodo(int n);  // Constructor por defecto
  nodo(const nodo &a);  // Constructor de copia
  void visita(int x);  // Vista la ciudad x
  void sig_etapa();  // Pasa a la siguiente etapa
  void fija_distancia(float a);  // Fija la distancia
  float distancia();  // Devuelve la distancia recorrida
  bool visitado(int x);  //Comprueba si se ha visitado x 
  bool solucion();  // Mira si ha terminado el viaje
};
\end{lstlisting}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{El problema de la mochila entera}
\framesubtitle{Algoritmo con ramificación y poda}
La siguiente función en C++ resuelve el problema del viajante con la técnica de ramificación y poda:
\begin{lstlisting}
nodo* camino_minimo(int n){
  priority_queue<node*, vector<node*>, menor_pri> c;
  nodo raiz(n);
  raiz.sig_etapa();
  c.push(&raiz);
  nodo *hijo, *nodoexp, *sol;
  sol = new nodo(n);
  sol->fija_distancia(DMAX);
  while (!c.empty()){
    nodoexp = c.top();
    c.pop();
\end{lstlisting}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{El problema de la mochila entera}
\framesubtitle{Algoritmo con ramificación y poda}
\begin{lstlisting}
if (nodoexp->distance() < sol->distance())
      for (int j=1; j<n; j++)
        if (!nodoexp->visitado(j)){ 
          hijo = new nodo(*nodoexp); hijo->visita(j);
          if (hijo->distancia() < sol->distancia())
            if (hijo->solucion()){
              hijo->visita(0);
              if (hijo->distancia() < sol->distancia())
                sol = hijo;
            }
            else c.push(hijo);
          else delete hijo;
        }
    delete nodoexp;
  }
  return sol;
}
\end{lstlisting}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema del viajante}
\framesubtitle{Ejemplo de ramificación y poda}
Para nuestro ejemplo, esta función realizaría el siguiente recorrido del espacio de búsqueda:
\begin{center}
\newcommand{\Tlabel}[1]{\tlput{\footnotesize #1}}
\pstree[thislinestyle=none,thislevelsep=0]{}{
\pstree[nodesep=2pt,levelsep=1cm,arrows=->,treenodesize=0.5cm]{\TR{0}}{ 
	\pstree{\TR{1}\Tlabel{3}}{
       \pstree{\TR{2}\Tlabel{7}}{
       		\pstree{\TR{3}\Tlabel{13}}{
       			\pstree[linestyle=none,arrows=none]{\TR{0}\Tlabel{15}}{\TR{15}\tvput{\rule{1cm}{0.2pt}}} } }
       \pstree[linestyle=dashed,linecolor=orange]{\TR{3}\Tlabel{$\infty$}}{
       		\pstree{\TR{2}}{
       			\TR{0}
       		}
       	}
	}
	\pstree[linestyle=dashed,linecolor=orange]{\TR{2}\Tlabel{$\infty$}}{
       \pstree{\TR{1}}{
       		\pstree{\TR{3}}{
       			\TR{0}
       		}
       	}
       	\pstree{\TR{3}}{
       		\pstree{\TR{1}}{
       			\TR{0} 
       		} 
       	}
	} 	
    \pstree{\TR{3}\Tlabel{3}}{ 
    	\pstree{\TR{1}\Tlabel{8}}{ 
    		\pstree{\TR{2}\Tlabel{12}}{ 
    			\pstree[linestyle=none,arrows=none]{\TR{0}\Tlabel{14}}{\TR{\fbox{\color{red}14}}\tvput{\rule{1cm}{0.2pt}}} } 
    		} 
    	\pstree{\TR{2}\Tlabel{7}}{ 
    		\pstree{\TR{1}\Tlabel{13}}{
       			\pstree[linestyle=none,arrows=none]{\TR{0}\Tlabel{18}}{\TR{18}\tvput{\rule{1cm}{0.2pt}}}
       		}
       	}
	}
}
\pstree[linestyle=none,nodesep=2pt,levelsep=1cm]{\TR{Origen}}{
	\pstree{\TR{1ª visita}}{
		\pstree{\TR{2ª visita}}{
			\pstree{\TR{3ª visita}}{
			 	\pstree{\TR{Destino}}{\TR{Distancia}}
			 }
		}
	}
}
}
\end{center}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema del viajante}
\framesubtitle{Mejora de la poda}
Se puede conseguir una poda más efectiva del espacio de búsqueda si se calcula
la cota inferior del coste del camino mínimo reduciendo la matriz de adyacencia.

\medskip
Una matriz reducida es una matriz cuyos elementos son no negativos y además,
cada fila y cada columna contiene al menos un 0.

\medskip 
Se puede reducir una matriz restando cantidades constantes a los elementos de
sus filas o columnas. En tal caso, si se resta la misma constante $c$ a todos
los elementos de una fila o columna de la matriz de adyacencia, cualquier
circuito hamiltoniano se verá reducido en dicha cantidad $c$. 

\medskip
En consecuencia,
se puede utilizar la suma de constantes utilizadas en la reducción de la matriz de
adyacencia como cota inferior de la distancia mínima.  
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema del viajante}
\framesubtitle{Reducción de la matriz de adyacencia}
Consideremos la matriz de adyacencia del ejemplo:
\[
\left(
\begin{array}{cccc}
\infty & 3 & \infty & 3 \\
5 & \infty & 4 & \infty \\
2 & 6 & \infty & 6 \\
2 & 5 & 4 & \infty
\end{array}
\right)
\]
Para reducir la primera fila, tomamos como $c$ el mínimo elemento de dicha fila
y lo restamos a toda la fila
\[
\left(
\begin{array}{cccc}
\infty & 3 & \infty & 3 \\
5 & \infty & 4 & \infty \\
2 & 6 & \infty & 6 \\
2 & 5 & 4 & \infty
\end{array}
\right)
\stackrel{\mbox{\footnotesize Fila 1 $c=3$}}{\longrightarrow}
\left(
\begin{array}{cccc}
\infty & 0 & \infty & 0 \\
5 & \infty & 4 & \infty \\
2 & 6 & \infty & 6 \\
2 & 5 & 4 & \infty
\end{array}
\right)
\]

Y la cota inferior del camino mínimo es 3.
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema del viajante}
\framesubtitle{Reducción de la matriz de adyacencia}
\[
\left(
\begin{array}{cccc}
\infty & 0 & \infty & 0 \\
5 & \infty & 4 & \infty \\
2 & 6 & \infty & 6 \\
2 & 5 & 4 & \infty
\end{array}
\right)
\stackrel{\mbox{\footnotesize Fila 2 $c=4$}}{\longrightarrow}
\left(
\begin{array}{cccc}
\infty & 0 & \infty & 0 \\
1 & \infty & 0 & \infty \\
2 & 6 & \infty & 6 \\
2 & 5 & 4 & \infty
\end{array}
\right)
\]
\[
\left(
\begin{array}{cccc}
\infty & 0 & \infty & 0 \\
1 & \infty & 0 & \infty \\
2 & 6 & \infty & 6 \\
2 & 5 & 4 & \infty
\end{array}
\right)
\stackrel{\mbox{\footnotesize Fila 3 $c=2$}}{\longrightarrow}
\left(
\begin{array}{cccc}
\infty & 0 & \infty & 0 \\
1 & \infty & 0 & \infty \\
0 & 4 & \infty & 4 \\
2 & 5 & 4 & \infty
\end{array}
\right)
\]
\[
\left(
\begin{array}{cccc}
\infty & 0 & \infty & 0 \\
1 & \infty & 0 & \infty \\
0 & 4 & \infty & 4 \\
2 & 5 & 4 & \infty
\end{array}
\right)
\stackrel{\mbox{\footnotesize Fila 4 $c=2$}}{\longrightarrow}
\left(
\begin{array}{cccc}
\infty & 0 & \infty & 0 \\
1 & \infty & 0 & \infty \\
0 & 4 & \infty & 4 \\
0 & 3 & 2 & \infty
\end{array}
\right)
\]
Esta matriz ya está reducia, y la suma total de las constantes restadas es
$3+4+2+2=11$, que es una cota inferior del camino mínimo. 
Utilizando esta cota como la prioridad de cada nodo, la poda es mucho mayor y
el algoritmo más eficiente. 
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema del viajante}
\framesubtitle{Cálculo de la cota a partir de la matriz reducida}
Veamos cómo calcular la cota inferior para los nodos distintos del raíz.

\medskip
Supongamos que $A$ es la matriz de adyacencia reducida para un nodo $x$, y sea
$y$ el nodo hijo de $x$ que se obtiene al incluir la arista $(i,j)$ en el
recorrido. Entonces para calcular la cota inferior del nodo y, hay que seguir los pasos siguientes: 
\begin{itemize}
\item Cambiar todos los elementos de la fila $i$ y la columna $j$ de $A$ por $\infty$.
\item Reducir la matriz $A$ con excepción de las filas $i$ y $j$. 
\item La cota del nodo y es la suma de la cota del nodo $x$, $A(i,j)$ y las
constantes restadas al reducir $A$.
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema del viajante}
\framesubtitle{Ejemplo del cálculo de la cota}
\begin{center}
\pstree[thislinestyle=none, thislevelsep=0.8cm]{
	\TR{$\footnotesize\left(\begin{array}{cccc}
	\infty & 0 & \infty & 0 \\
	1 & \infty & 0 & \infty \\
	0 & 4 & \infty & 4 \\
	0 & 3 & 2 & \infty
	\end{array}\right)$}}{
		\pstree[nodesep=2pt,levelsep=1cm,arrows=->,treenodesize=0.5cm]{\TR{0}}{ 
			\pstree[linestyle=none,arrows=-,nodesep=2pt,levelsep=1cm]{\TR{1}\tlput{\footnotesize 3}}{
				\pstree{\TR{$\footnotesize\left(\begin{array}{cccc}
					\infty & \infty & \infty & \infty \\
					1 & \infty & 0 & \infty \\
					0 & \infty & \infty & 0 \\
					0 & \infty & 2 & \infty
					\end{array}\right)$}}
					{Cota=11+0+4}
			}
			\pstree[linestyle=none,arrows=-,nodesep=2pt,levelsep=1cm]{\TR{2}\trput{\footnotesize $\infty$}}{
				\pstree{\TR{$\footnotesize\left(\begin{array}{cccc}
					\infty & \infty & \infty & \infty \\
					0 & \infty & \infty & \infty \\
					0 & 1 & \infty & 0 \\
					0 & 0 & \infty & \infty
					\end{array}\right)$}}
					{Cota=11+0+8}
			}
			\pstree[linestyle=none,arrows=-,nodesep=2pt,levelsep=1cm]{\TR{3}\trput{\footnotesize 3}}{
				\pstree{\TR{$\footnotesize\left(\begin{array}{cccc}
					\infty & \infty & \infty & \infty \\
					1 & \infty & 0 & \infty \\
					0 & 1 & \infty & \infty \\
					0 & 0 & 2 & \infty
					\end{array}\right)$}}
					{Cota=11+0+3}
			}
     	}
  
	}
\end{center}
\end{frame} 


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema del viajante}
\framesubtitle{Ejemplo de ramificación y poda}
Para nuestro ejemplo, con esta otra cota se realizaría el siguiente recorrido el espacio de búsqueda:
\begin{center}
\pstree[thislinestyle=none,thislevelsep=0]{}{
\pstree[nodesep=2pt,levelsep=1cm,arrows=->,treenodesize=0.5cm]{\TR{0}}{ 
	\pstree[linestyle=dashed,linecolor=orange]{\TR{1}\tlput{\footnotesize 15}}{
       \pstree{\TR{2}}{
       		\pstree{\TR{3}}{
       			\TR{0}
			}
       }
       \pstree{\TR{3}}{
       		\pstree{\TR{2}}{
       			\TR{0}
			}
       }
	}
	\pstree[linestyle=dashed,linecolor=orange]{\TR{2}\trput{\footnotesize$\infty$}}{
       \pstree{\TR{1}}{
       		\pstree{\TR{3}}{
       			\TR{0}
       		}
       	}
       	\pstree{\TR{3}}{
       		\pstree{\TR{1}}{
       			\TR{0} 
       		} 
       	}
	} 	
    \pstree{\TR{3}\trput{\footnotesize 14}}{ 
    	\pstree{\TR{1}\tlput{\footnotesize 14}}{ 
    		\pstree{\TR{2}\tlput{\footnotesize 14}}{ 
    			\pstree[linestyle=none,arrows=none]{\TR{0}\tlput{\footnotesize 14}}{\TR{\fbox{\color{red}14}}\tvput{\rule{1cm}{0.2pt}}} } 
    		} 
    	\pstree[linestyle=dashed,linecolor=orange]{\TR{2}\trput{\footnotesize 18}}{ 
    		\pstree{\TR{1}}{
       			\TR{0}
       		}
       	}
	}
}
\pstree[linestyle=none,nodesep=2pt,levelsep=1cm]{\TR{Origen}}{
	\pstree{\TR{1ª visita}}{
		\pstree{\TR{2ª visita}}{
			\pstree{\TR{3ª visita}}{
			 	\pstree{\TR{Destino}}{\TR{Distancia}}
			 }
		}
	}
}
}
\end{center}
\end{frame}


